package DP;

import org.junit.Test;

/**
 * @Classname JZ10斐波那契数列
 * @Description TODO
 * @Date 2022/12/21 11:23
 * @Created by xjl
 */
public class JZ10斐波那契数列 {

    /**
     * @description 采用的地推的思想 但是这样是的超过内存限制
      * @param: n
     * @date: 2022/12/21 11:24
     * @return: int
     * @author: xjl
    */
    public int fib(int n) {
        if (n<2){
            return n;
        }
        return fib(n-2)+fib(n-1);
    }

    public int fib2(int n) {
        final int MOD = 1000000007;
        if (n < 2) {
            return n;
        }
        int a = 0, b = 0, c = 1;
        for (int i = 2; i <= n; ++i) {
            a = b;
            b = c;
            c = (a + b) % MOD;
        }
        return c;
    }

    @Test
    public void test(){
        int i = fib2(7);
        System.out.println(i);
    }
}
